package code.starivan.niuke.jianoffer;

import java.util.ArrayList;

import java.util.Stack;
/**
 * Created by Ivan on 2015/8/24.
 */
public class FindTreePath {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        if(root==null)
            return list;

        Stack<TreeNode> nodes=new Stack<>();
        findPath(root,target,0,nodes,list);
        return list;
    }

    private void findPath(TreeNode node,int target,int currSum,Stack<TreeNode> nodes,ArrayList<ArrayList<Integer>> list){
        currSum+=node.val;
        nodes.push(node);

        boolean isLeaf=node.left==null&&node.right==null;
        if(currSum==target&&isLeaf){
            ArrayList<Integer> data=new ArrayList<>();
            for(TreeNode n:nodes){
                data.add(n.val);
            }

            list.add(data);
        }

        if(node.left!=null){
            findPath(node.left, target, currSum, nodes, list);
        }
        if(node.right!=null){
            findPath(node.right,target,currSum,nodes,list);
        }

        nodes.pop();
    }
}
